import java.util.*;

/**
 * @Author Fizz Pu
 * @Date 2020/10/8 下午7:21
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class LeeOffer38 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] arr = solution.permutation("aa");
        System.out.println(Arrays.toString(arr));
    }
}


class Solution {
    List<String> res = new LinkedList<>();
    String inner = "";
    public String[] permutation(String s) {
        boolean[] visited = new boolean[s.length()];
        Arrays.fill(visited, 0, s.length(), false);
        traceBack(s, 1, visited);
        return res.toArray(new String[res.size()]);
    }

    void traceBack(String s, int height, boolean[] visited){
        int len = s.length();
        if(height > len){
            res.add(inner);
            return;
        }
        Set<Character> temp = new HashSet<>();
        for(int i = 0; i < len; ++i){
            char ele = s.charAt(i);
            if(!visited[i] && !temp.contains(ele)){
                temp.add(ele);
                visited[i] = true;
                inner += ele;
                traceBack(s, height+1, visited);
                visited[i] = false;
                inner = inner.substring(0, inner.length()- 1);
            }
        }
    }
}